package com.xy6.struct.stack;



/**
 * 栈
 * <p>基于链表实现
 * <p>与<code>ListedList</code>实现基本一致
 * 
 * @author zhang
 * @since 2017-09-03
 */
public class Stack2<T> {
	
	/**
	 * 元素总数
	 */
	private int size = 0;
	
	/**
	 * 第一个元素
	 */
	private Node<T> first;
	
	/**
	 * 最后一个元素
	 */
	private Node<T> last;
	
	public Stack2(){
	}
	
	/**
	 * 新增一个元素
	 * <p>在末尾新增
	 * 
	 * @param o
	 * @return
	 */
	public boolean push(T o){
		linkLast(o);
		return true;
	}
	
	public T pop(){
		T item = last.item;
		unlink(last);
		
		return item;
	}
	
	/**
	 * 链表元素个数
	 * 
	 * @return
	 */
	public int size(){
		return size;
	}
	
	/**
	 * 清空集合元素
	 */
	public void clear(){
        for (Node<T> x = first; x != null; ) {
            Node<T> next = x.next;
            x.item = null;
            x.next = null;
            x.pre = null;
            x = next;
        }
        first = last = null;
        size = 0;
	}
	
	public void print(){
		for (Node<T> x = first; x != null; x = x.next) {
			System.out.print(x.item + " ");
		}
		System.out.println();
	}
	
	/**
	 * 删除一个节点
	 * 
	 * @param o
	 */
	private void unlink(Node<T> o){
		if(o == null){
			return;
		}
		Node<T> pre = o.pre;
		Node<T> next = o.next;
		if(pre == null){
			first = next;
		} else {
			pre.next = next;
		}
		if(next == null){
			last = pre;
		} else {
			next.pre = pre;
		}
		
		o.pre = null;
		o.next = null;
		o.item = null;
		o = null;
		size --;
	}
	
	/**
	 * 在链表最后插入一个元素
	 * 
	 * @param elem
	 */
	@SuppressWarnings({ "rawtypes", "unchecked" })
	private void linkLast(T elem){
		Node<T> l = last;
		Node<T> newNode = new Node(l, elem, null);
		last = newNode;
		if(l == null){
			first = newNode;
		} else {
			l.next = newNode;
		}
		size++;
	}
	
	/**
	 * 链表中节点bean
	 * <p>每个节点都有两个指针，一个指向前一个元素，一个指向后一个元素
	 * 
	 * @param <T>
	 */
	private static class Node<T> {
		T item;
		Node<T> pre;
		Node<T> next;
		
		public Node(Node<T> pre, T elem, Node<T> next){
			this.pre = pre;
			this.item = elem;
			this.next = next;
		}
	}
	
}
